模拟赛题解/2025.9.22 模拟赛

T1-题意（orchestra）

题面

给定一串长度为 $n$ 的数对序列 $(x_i,y_i)$，其中 $x_i,y_i$ 都是整数。

有 $m$ 次询问，每次给定两个整数 $a,b$，你需要先选定一个整数 $k$（注意 $k$ 可以为 $0$），然后再选定一个正整数序列 $1\leq p_1\leq p_2\leq\cdots\leq p_k\leq n$（若 $k=0$ 则该序列为空），使得

$$min\left(a+\sum_{i=1}^k x_{p_i},b+\sum_{i=1}^k y_{p_i}\right)$$

最大，输出这个最大值。

$1\leq n\leq 10^3,0\leq\sum|x_i|\leq10^5,0\leq\sum|y_i|\leq10^{12},1\leq m\leq2\times10^5,1\leq|a_i|,|b_i|\leq10^{12}$。

题解

首先把 $a$ 提出来，发现此时 $x$ 部分固定了。

并且 $x$ 的值域只有区区 $10^5$，于是我们考虑用类似于背包的方式，用 $f_i$ 表示 $\sum_{j=1}^k x_{p_j}=i$ 的时候 $\sum_{j=1}^k y_{p_j}$ 的最大取值。

最小值最大容易想到二分答案，于是二分判定是否可行。

复杂度 $O((n+m)\log\sum x_i)$。

T2-戏已完结（plaudite）

题面

给定两个正整数 $n,m$，其中 $n\leq m$。

我们称长度为 $n$ 的非负整数序列 $a=(a_1,a_2,\cdots,a_n)$ 满足以下条件是良好序列：

• $0\leq a_1\leq a_2\leq\cdots\leq a_n\leq m$。

对于一个良好序列 $a$，定义函数 $f(a)$，其生成的序列如下：

$$f(a)=sort(a_1-1,a_2-2,\cdots,a_n-n)$$

即将序列 $(a_1-1,a_2-2,\cdots,a_n-n)$ 进行升序排序后得到 $f(a)$。

接下来有 $q$ 个询问，每个询问给定 $k$，求：

• 计算所有可能的良好序列 $a$ 对应的 $f(a)$ 中第 $k$ 个元素的总和，并输出该值对 $998244353$ 取模后的结果。

tips：可能对解题有用的定理

在一个 $n\times n$ 的网格中，我们称 $(i,j)\rightarrow (i+1,j)$ 这一步为一个横线，所有 $(0,0)\rightarrow(n,n)$（只能向上或者向右走）的路径中，设恰好有 $k$ 条横线在 $y=x$ 直线上方（即横线两端点均在直线上或上方）的路径有 $c_k$ 个，那么所有 $c_k$ 相等。

$1\leq k\leq n\leq m\leq 10^5,1\leq q\leq10^4$。

题解

考虑转化成一个格路计数问题：

• 有一个 $n \times m$ 的网格，每次可以往上或往右走，要从 $(0,0)$ 走到 $(n,m)$。
• 每次从 $(i,j) \to (i+1,j)$ 就确定了 $a_{i+1} = j$，称 $(i,j) \to (i+1,j)$ 为斜线。
• 对于某个 $x+i(k-1)$，可以转化到斜线：画出 $y=x+k(-n \leq k \leq m)$ 的所有斜线，对于每条斜线，若有一个横线在它的上方经过，则将 $ans_{n-k+1}\dots ans_m$ 加上 1。

考虑对于每条斜线贡献时，我们想要求对于每个 $i$ 计算，有多少个方案恰好有 $c$ 个横线在它的上方经过。

先将对路径斜线转化为路径斜线的情形，这部分贡献可以 $O(n)$ 算出。

枚举某条斜线上的前两个位置，设这这是路径的第 $c$ 次、最后一次触碰斜线的位置。

我们有结论：

• 在一个 $n \times m$ 的网格从 $(0,0)$ 走到 $(n,n)$，设所有 $(i,j) \to (i+1,j)$ 在对角线上方经过的次数为 $c$ 的方案数是 $ans_c$，则所有 $c$ 相等，均为 $\binom{n}{n+1}$。

于是设定第一次、最后一次触碰斜线位置后，可贡献的 $c$ 是一个区间，因为区间中的每个 $c$ 贡献相等。

直接枚举答案复杂度是 $O(n^3)$，考虑如何优化。

把 $x=k$ 的直线分成 $k \in [0,m-n]$ 和 $k \in [-(n-1),-1]$ 两部分。$[m-n+1,m]$ 和 $[-(n-1),-1]$ 是对称的。

考虑 $k \in [-(n-1),-1]$ 的部分。

假设我们枚举了触碰起始点之间的长度 $len$，则任意分数组上的修改位置是确定的。

枚举 $len$，那么段触碰起始点之间的方案是固定的，前后两段的形式都是 $(0,0) \to (a,b)$ 且不触碰 $y=x+(b+1-a)$ 的折线计数（假设把后一段对称一下）。

把这两段拆开挂起来，就变成了一段折线，形式也是 $(0,0) \to (a,b)$ 且不触碰 $y=x+(b+1-a)$，且 $(a,b)$ 是很左很左的点。这部分的方案数就变成了两个组合数根据 $len$ 的形式。

再枚举所有的 $k$ 加起来，发现加和的式子能拆掉，可以 $O(1)$ 计算同一个 $len$ 的方案数。于是这部分能做到 $O(n)$。

考虑 $k \in [0,m-n]$ 的部分。

由于我们只需考虑分数组上修改权，所以可以只关心：对于所有触碰起点 $k$ 点，其方案数之和，起点和终点由 $len$ 决定，不再考虑起点。

由于起终点之间的方案数就是 $\binom{2len}{len}/(len+1)$ 的形式，我们代入这些部分全部在斜线上面走。那折线就变成了从 $(0,0)$ 到起点是走最短路径，走上去到 $(n,m)$ 并且不穿过斜线。

这样也是两段 $(0,0)\to (a,b)$ 不触碰 $y=x+(b+1-a)$ 的形式，可以把两段折线拼起来，贡献就是两个组合数相乘。

枚举所有的 $k$ 加起来，发现要求若干个如下的形式：

$$\sum_{p=0}^{m-n} \binom{2p+k}{p} \binom{n+m+k-2p}{n-p}$$

观察一下，发现上面加起来是常数，下面加起来也是常数。把这个看作要求

$$\sum_{i=1}^r \binom{i}{k} \binom{n-i}{m-k}.$$

先考虑 $\sum_{i=0}^n \binom{i}{k}\binom{n-i}{m-k}$。若考虑 $n \to p+1$，则 $m,n$ 不会修改，$k$ 有 $O(1)$ 的变化，于是式子可以 $O(1)$ 维护。

增大了，显然只需要加上一项。

• 增大 $k$ 的话，考虑这个式子的组合含义是在 $n$ 个白球中染黑 $m$ 个，且第 $k$ 个黑球的位置 $\leq r$。 若 $k \to k+1$，限制变成第 $k+1$ 个黑球的位置 $\leq r$，需要减少第 $k+1$ 个黑球位置 $>r$ 的情况。

于是这部分也能做到 $O(n)$。

T3-运输规划（xor）

题面

在数轴上依次排列着 $n$ 个工厂，从左到右第 $i$ 个工厂有 $a_i$ 单位货物。

商人蛋蛋拥有 $2^m$ 种货车，编号为 $0,1,\cdots,2^m-1$。若使用编号为 $j$ 的货车运输 $x$ 单位货物，则能获得的收益为：$x\oplus j$。

其中 $\oplus$ 表示按位异或，$m$ 为给定常数。

现在有 $q$ 次独立的运输计划，对于第 $t$ 次计划，蛋蛋只知道货车会前往某个工厂，工厂编号在区间 $[l,r]$ 之间（包含两端）。在计划开始前，蛋蛋可以从所有货车中任选一种。

蛋蛋想知道：在最优选择下，每次运输在最坏情况下会获得多少收益。

$1\leq n\leq10^5,1\leq m\leq50,1\leq q\leq5\times10^5,0\leq a_i\leq2^m,1\leq l\leq r\leq n$。

题解

肯定不能枚举端点。考虑在 trie 树上干点什么东西。令 $f_p$ 为 trie 树上节点 $p$ 的答案，$dep_p$ 为其深度，则：

f_p = \begin{cases} \max(f_{ls}, f_{rs}) & (ls \wedge rs) \$$6pt] f_{son} + 2^{m-dep_p} & \text{otherwise} \end{cases}

答案就是根节点的 dp 值。

枚举左端点，移动右端点，加入一个点只会修改 $m$ 个位置的 dp 值，$O(n^2 m + q)$。

再进一步，直接莫队，$O(nm \sqrt{q})$。

$n$ 相比 $q$ 很小，考虑从 $n$ 下功夫，即每个位置对答案的贡献。

换一种方法描述上面的 dp：选择一个值，从 trie 树上代表这个值的节点一直往上跳，没有兄弟就把和加上 $2^k$，求最⼤邻和。

显然这个值只会存在于区间内，因为空节点的 dp 值一定为 $0$。

对于 $i$ 的深度为 $j$ 的祖先的兄弟，设这个兄弟子树内点的集合为 $S$，则区间需要包含 $i$ 而不包含 $S$ 内任意的数，$i$ 对这个区间的贡献的第一个 $m-k$ 位才是 1。显然我们只需要知道 $S$ 里的前驱与后继 $(s,t)$，区间的范围为 $s<l \leq i \leq r < t$。

因为只有两个祖先，所以只有两个对 $(s,t)$，所以对于一个 $i$，把所有区间分成了 $m^2$ 种不同的贡献（左边 $m$ 种，右边 $m$ 种）。一个相同形式区间记作 $[x_1,x_2], r=[y_1,y_2]$。这个限制并不好做，因为涉及到 $l,r$。但是不难证明直接按 $x_1<l \leq r < y_2$ 做是对的。因为缩小区间会使实际答案变⼩，而不会变⼤，一定不优。

于是直接扫描线，$O(nm^2 \log n + q \log n)$。

最后考虑用分块平衡，做到 $O(nm^2+q\sqrt{n})$。搞笨的，直接树状数组差不多能直接过（官方数据并没有卡，感觉也难卡，所以干脆放了）。

其实要慢代码慢的地方是 $nm^2$ 的双 vector 遍历。

T4-不吼不叫（string）

题面

小 A 有一个初始字符串 $t$。他希望通过一系列操作将 $t$ 转换为目标字符串 $s$。每次操作，他可以选择切掉 $t$ 的一个前缀或一个后缀，但必须满足以下条件：切掉的前缀或后缀必须是操作后剩余字符串的子串。也就是说，如果切掉前缀 $p$ 后剩余字符串为 $t'$，那么 $p$ 必须是 $t'$ 的一个连续子串；同样，如果切掉后缀 $suf$ 后剩余字符串为 $t'$，那么 $suf$ 必须是 $t'$ 的一个连续子串。

小 A 想知道最少需要多少次操作才能从 $t$ 得到 $s$。如果无法通过任何操作序列得到 $s$，则输出 $-1$。

$1\leq|s|\leq|t|\leq5\times10^3$，字符集 $\in[\text{a},\text{z}]$。

题解

正难则反，将切除操作改为添加，很显然尽可能大地添加字符段最优。

所以维护 $f_{i,j}$ 表示以 $i,j$ 为右端点的最长公共后缀，同理维护 $g_{i,j}$ 表示以 $i,j$ 为左端点的最长公共前缀。

同时，维护 $l_{i,j}/r_{i,j}$ 表示区间 $[l,r]$ 能向左/向右添加的最长段落长度。

从 $s$ 在 $t$ 中的子串位置开始，做一个类似多元最短路的操作即可。

复杂度 $O(n^2)$。